class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null)
            return root;
        TreeNode left =  invertTree(root.left);
        TreeNode right =  invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null)
            return root;
        Deque<TreeNode> q = new LinkedList<>();
        q.add(root);
        while( !q.isEmpty() ){
            TreeNode head = q.pop();
            TreeNode tmp = head.left;
            head.left = head.right;
            head.right = tmp;
            
            if( head.left!=null ){
                q.add(head.left);
            }
            if( head.right!=null ){
                q.add(head.right);
            }
        }
        return root;
    }
}